package ebook.datastructure.typed.chapter9;

import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * description: <br>
 * createTime: 2020/8/2814:26 <br>
 *
 * @author zzh
 */
//TODO 待完成
public class RedBlackTree<T extends Comparable> {
    RedBlackNode<T> root;

    public RedBlackTree () {}

    public void addNode(T t) {
        RedBlackNode<T> node = new RedBlackNode<>();
        node.setValue(t);
        if(root == null) {
            // 没有根节点，则设置为黑色，作为根节点
            root = node;
            root.setRed(false);
        } else {
            node.setRed(true);
            // 查找插入点插入
            linkedToNode(node, root);
        }
    }


    private void linkedToNode(RedBlackNode<T> node, RedBlackNode<T> parent) {
        //TODO 检查刚过的祖父节点是否有两个红色节点，有的话，要进行颜色变换
        RedBlackNode<T> grandPa = parent.getParent();
        if(grandPa != null) {
            if(grandPa.getLeft() != null && grandPa.getLeft().isRed() && grandPa.getRight() != null && grandPa.getRight().isRed()) {
                grandPa.getLeft().flip();
                grandPa.getRight().flip();
                if(grandPa.getParent() != null) {
                    // 非根节点的祖父节点也要变色
                    grandPa.flip();
                }
                //TODO 变换颜色后，可能导致祖父节点与其父节点颜色同为红色，则需要进行两次旋转
            }
        }
        // 大于，等于放在右子节点
        if(parent.getValue().compareTo(node.getValue()) <= 0) {
            if(parent.getRight() == null) {
                //TODO 找到插入点，检查颜色，做改变颜色和旋转等操作，保证红黑树符合基本规则
                if(!parent.isRed()) {
                    parent.setRight(node);
                } else {
                    if(grandPa == null) {
                        parent.setRight(node);
                    }else {

                    }
                }
            } else {
                linkedToNode(parent.getRight(), node);
            }
        } else {
            if(parent.getLeft() == null) {
                //TODO 找到插入点，检查颜色，做改变颜色和旋转等操作，保证红黑树符合基本规则
                parent.setLeft(node);
            } else {
                linkedToNode(parent.getLeft(), node);
            }
        }
    }


    @Data
    @NoArgsConstructor
    public class RedBlackNode <T extends Comparable> {
        boolean isRed;
        T value;
        RedBlackNode<T> parent;
        RedBlackNode<T> left;
        RedBlackNode<T> right;


        public void setLeft(RedBlackNode<T> left) {
            this.left = left;
            left.setParent(this);
        }


        public void setRight(RedBlackNode<T> right) {
            this.right = right;
            right.setParent(this);
        }


        public void flip() {
            isRed = !isRed;
        }
    }
}
